package com.leetcode.algorithm.y22.m06;

/**
 * 746. 使用最小花费爬楼梯
 * 
 * https://leetcode.cn/problems/min-cost-climbing-stairs/
 * 
 * @author jie.deng
 *
 */
class Question0746Solution01 {

	public int minCostClimbingStairs(int[] cost) {
		int len = cost.length;

		// DP状态定义
		int[] dp = new int[len];

		// DP状态初始化
		dp[0] = cost[0];
		dp[1] = cost[1];

		// 状态转移方程：
		for (int i = 2; i < len; i++) {
			dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
		}

		return Math.min(dp[len - 1], dp[len - 2]);
	}

}